package algorithm;

public class leetcode_0091 {
    public int numDecodings(String s) {
        int len=s.length();
        int [] dp=new int[len];
        if(len==0) return 0;
        if(len==1) {
            if("0".equals(s)) {return 0;}
            return 1;
        }
        if(s.charAt(0)!='0') dp[0]=1;
        trans(dp,len,1,s);
        return dp[len-1];
    }
    public void trans(int [] dp,int len,int index,String s){
        for(int i=1;i<len;++i){
            if(s.charAt(i)!='0'){
                dp[i]+=dp[i-1];
            }
            if(i==1){
                if(s.charAt(0)!='0'&&((s.charAt(0)-'0')*10+(s.charAt(1)-'0'))<=26) dp[i]+=1;
            }
            else{
                if(s.charAt(i-1)!='0'&&((s.charAt(i-1)-'0')*10+(s.charAt(i)-'0'))<=26) dp[i]+=dp[i-2];
            }
        }
    }

}
